package __sort

// Heap 最大堆实现
// 完全二叉树：从左往右节点依次添加数据
// 堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
// 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
// 左右哪个小哪个大没有要求
type Heap struct {
	Size int
	// 使用内部的数组来模拟树
	// 一个节点下标为 i，那么父亲节点的下标为 (i-1)/2
	// 一个节点下标为 i，那么左儿子的下标为 2i+1，右儿子下标为 2i+2
	Array []int
}

func NewHeap(arr []int) *Heap {
	return &Heap{
		Size:  0,
		Array: arr,
	}
}

// Push 入堆操作
// 先将数字放到堆尾，与父类进行比较
// 如果父类较小，则交换位置，直到不交换为止
func (h *Heap) Push(x int) {
	if h.Size == 0 {
		h.Array[0] = x
		h.Size++
		return
	}
	// 如果有元素，那么先将元素的位置指向最后，然后上浮
	i := h.Size
	// 与父类比较
	for i > 0 {
		parentIndex := (i - 1) >> 1
		// 判断小于等于父节点
		if x <= h.Array[parentIndex] {
			break
		}
		// 交换位置
		h.Array[i] = h.Array[parentIndex]
		i = parentIndex
	}
	// 直到不交换
	h.Array[i] = x
	h.Size++
}

// Pop 弹出操作
// 弹出第一个值（即最小值）
// 将堆尾的数字移动到顶部，与子节点中较大的交互位置，直到不交换为止
func (h *Heap) Pop() int {
	// 如果没有元素，返回-1
	if h.Size == 0 {
		return -1
	}
	// 先保存好要弹出的最大数
	ret := h.Array[0]
	// 先减减，因为后面要用来判断
	h.Size--
	// 堆尾的数
	x := h.Array[h.Size]
	i := 0
	for i < h.Size {
		left := (2 * i) + 1  // 左节点
		right := (2 * i) + 2 // 右节点
		// 没有左节点，也不会有右节点
		if left >= h.Size {
			break
		}
		// 如果有右节点,找到大的那一个
		if right < h.Size && h.Array[right] > h.Array[left] {
			left = right
		}
		// 最终都拿着left去比较，就不用管只有左节点，没有右节点的情况
		if h.Array[left] <= x {
			break
		}
		// 将较大的元素上浮
		h.Array[i] = h.Array[left]
		i = left
	}
	// 将最后一个元素的值 x 放在不会再翻转的位置
	h.Array[i] = x
	return ret
}
